package com.hy;

import java.util.*;

/**
 * Created With IntelliJ IDEA.
 * Descriptions:  括号生成
 * 数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
 * 示例 1：
 *
 * 输入：n = 3
 * 输出：["((()))","(()())","(())()","()(())","()()()"]
 * 示例 2：
 *
 * 输入：n = 1
 * 输出：["()"]
 *
 * author: Mr.Du
 * Date: 2022/11/5
 * Time: 15:29
 */
public class GenerateParenthesis {
    
    public static void main(String[] args) {
        GenerateParenthesis generateParenthesis = new GenerateParenthesis();
        List<String> list = generateParenthesis.generateParenthesis(3);
        System.out.println(list);
    }
    
    List<String> res = new LinkedList<>();
    public List<String> generateParenthesis(int n) {
        dd(n,n,new StringBuffer());
        return res;
    }
    
    /**
     * 初始化left和right大小就是n
     * @param left      表示左括号剩余数
     * @param right     表述右括号剩余数
     * @param sb        结果集
     */
    public void dd(int left,int right,StringBuffer sb){
        if(right < left) return;
        if(left < 0 || right < 0) return;
        if(left == 0 && right == 0){
            // 左右都没有括号就添加
            res.add(sb.toString());
            return;
        }
        // 先加左括号--->  选择
        sb.append("(");
        // 递归
        dd(left-1,right,sb);
        // 回退
        sb.deleteCharAt(sb.length() - 1);
        
        // 再加有括号---> 选择
        sb.append(")");
        // 递归
        dd(left,right - 1,sb);
        // 回退
        sb.deleteCharAt(sb.length() - 1);
        
        
    }
}
